/**
 * @author Sebastian
 * @version 2.0
 * @date 2024/6/19 19:47
 */
// 寻找两个正序数组的中位数
// 给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
//
//算法的时间复杂度应该为 O(log (m+n)) 。
    // 把问题转化为两个有序数组找第k大的数
//原因：
//示例 1：
//
//输入：nums1 = [1,3], nums2 = [2]
//输出：2.00000
//解释：合并数组 = [1,2,3] ，中位数 2
//示例 2：
//
//输入：nums1 = [1,2], nums2 = [3,4]
//输出：2.50000
//解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
public class Solution4 {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int n = nums1.length + nums2.length;
        // 处理偶数情况
        if (n % 2 == 0) {
            // 分别记录左右数
            int left = findKth(nums1, 0, nums2, 0, n /2);
            int right = findKth(nums1, 0, nums2, 0, n/2  + 1);
            return (left + right) /2.0;
        } else {
            return findKth(nums1, 0, nums2, 0, n/2 + 1);
        }
    }

    // 找两个有序数组中第k大的数
    private int findKth(int[] nums1, int start1, int[] nums2, int start2, int k) {
        // 使nums1为较短的数组，方便处理
        if (nums1.length - start1 > nums2.length - start2) {
            return findKth(nums2, start2, nums1, start1, k);
        }
        // 如果nums1没有元素，直接返回nums2第k个元素
        if (nums1.length == start1) return nums2[start2 + k - 1];

        // 处理递归条件
        if (k == 1) return Math.min(nums1[start1], nums2[start2]);
        // 处理下标
        int idx1 = Math.min(nums1.length,start1 + k / 2);
        int idx2 = start2 + k - k / 2;
        if (nums1[idx1 - 1] < nums2[idx2 - 1]) {
            // 删掉idx1前面的
            return findKth(nums1, idx1, nums2, start2, k - (idx1 - start1));
        } else {
            return findKth(nums1, start1, nums2, idx2, k - (idx2 - start2));
        }
    }
}
